#include <stdio.h>

#include <iostream>
using namespace std;

template<class T>

int getLength(T& array){
    return sizeof(array)/sizeof(array[0]);
}

void printArray(int array[],int length){
    for(int i = 0; i < length; i++){
        cout<< array[i]<< " ,";
    }
    cout<<endl;
}

void copyArray(int nums[],int array[],int length){
    for (int i = 0; i < length; i++)
    {
        array[i] = nums[i];
    }
}

void swap(int nums[], int i, int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

/*******************************插入排序*******************************/
//直接插入排序
void insertSort(int nums[],int length){
    for (int i = 1; i < length; i++)
    {
        int temp = i;
        for (int j = i-1; j >= 0; j--)
        {
            if (nums[temp] > nums[j])
            {
                break;
            }else{
                nums[temp] = nums[j] + nums[temp];
                nums[j] = nums[temp] - nums[j];
                nums[temp] = nums[temp] - nums[j];
            }
            temp--;
        }
    }
}

/**
 *希尔排序： 
 * 思路：本质是直接插入排序,
 * 测试用例：{49 ,38, 65, 97, 76, 13, 27, 49, 55, 4}
 */
void xierSort(int nums[], int length, int gap){
    //经典希尔算法的gap值为 length/2，length/4
    for (; gap >= 1; gap/=2)
    {
        //使用直接插入排序
        for (int i = gap; i < length; i+=gap)
        {
            int temp = i;
            for (int j = i-gap; j >= 0; j-=gap)
            {
                if (nums[temp] > nums[j])
                {
                    break;
                }else{
                    nums[temp] = nums[j] + nums[temp];
                    nums[j] = nums[temp] - nums[j];
                    nums[temp] = nums[temp] - nums[j];
                }
                temp-=gap;
            }
        }
    }
}

/* 
 *折半插入排序 (nums原始数组已排序完成，num：待插入数据，length，数组长度)
 *思路：先二分查找到该插入的位置，然后插入
*/
void binarySort(int nums[], int length, int key){
    //1二分查找到目标位置
    int low = 0,high = length-2;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        cout<<"low:"<<low<<"high:"<<high<<"mid"<<mid;
        if (nums[mid] >= key && nums[mid-1] <= key)
        {
            //找到对应位置，开始执行插入
            for (int i = length-1; i > mid; i--)
            {
                nums[i] = nums[i - 1];
            }
            nums[mid] = key;
            break;
        }else if (nums[mid] < key)
        {
            low = mid + 1;
        }else if (nums[mid] > key)
        {
            high = mid - 1;
        }
    }
    
}

/*******************************交换排序*******************************/
/**
 * 冒泡排序：测试用例：{49 ,38, 65, 97, 76, 13, 27, 49, 55, 4};
 * 思路：两层循环，大数向后移动，小数向前移动
 * */
void bubbleSort(int nums[],int length){
    for (int i = 0; i < length; i++)
    {
        int temp = i;
        for (int j = temp+1; j < length; j++)
        {
            if (nums[j] < nums[temp])
            {
                nums[temp] = nums[j] + nums[temp];
                nums[j] = nums[temp] - nums[j];
                nums[temp] = nums[temp] - nums[j];
            }
            
        }
        
    }
    
}

/**
 * 快速排序：测试用例：{49 ,38, 65, 97, 76, 13, 27, 49, 55, 4};
 * 思路：递归，取一个数组nums的第一个元素a，将该数组的所有元素大于a的放到数组后面，小于a的放到前面
 * 如此不断循环
 * */
void quickSort(int nums[], int low, int high){
    if (low < high)
    {
        int i = low,j = high;
        int temp = nums[i];//定义一个哨兵元素
        while (i < j)
        {
            //从后往前找到第一个小于temp的元素
            while (i < j && temp < nums[j])
            {
                j--;
            }
            if(i < j){
                //找到小于temp的元素将其赋值给i
                nums[i] = nums[j];
                i++;
            }
            //从前往后找到第一个大于temp的元素
            while (i < j && temp > nums[i])
            {
                i++;
            }
            if(i < j){
                //找到小于temp的元素将其赋值给i
                nums[j] = nums[i];
                j--;
            }
            nums[i] = temp;
        }
        quickSort(nums, low, i-1);
        quickSort(nums, i+1, high);
    }
}

// quickSort:
// if(low < high){
//         int i = low, j = high, temp = nums[low];//定义数组第一元素为哨兵元素
//         while (i < j)//循环将数组中大于哨兵的元素放到后面去，将小于哨兵的元素放到前面去
//         {
//             while (i < j && nums[j] >= temp)j--;
//             //找到一个大于temp，但处于前面的元素，需要将其放到后面去
//             if (i < j)
//             {
//                 nums[i] = nums[j];
//                 // swap(nums,i,j);
//                 i++;
//             }
// 
//             while (i < j && nums[i] <= temp)i++;
//             //找到一个大于temp，但处于前面的元素，需要将其放到后面去
//             if (i < j)
//             {
//                 // swap(nums,i,j);
//                 nums[j] = nums[i];
//                 j--;
//             }
//             nums[i] = temp;
//         }
//         quickSort(nums,low,i-1);
//         quickSort(nums,i+1,high);
//     }


/*******************************选择排序*******************************/
/**
 * 简单选择排序：每次从待排序序列中选择一个最小值交换到待排序序列的起始位置
 * 思路：扫描待排序序列，从中找出最小的元素加入到已排序的序列中
 * */
void simpleSelectSort(int nums[] ,int length){
    for (int i = 0; i < length; i++)
    {
        int temp = i;
        //进行一次循环找出数组中最小的元素
        for (int j = i; j < length; j++)
        {
            if (nums[j] < nums[temp])
            {
                temp = j;
            }
        }
        int a = nums[temp],b=nums[i];
        swap(nums,temp,i);
        printArray(nums,length);
    }
}

/**
 * 堆排序：要求：1.完全二叉树，2.根节点大于两个孩子结点
 * */
void heapify(int tree[], int length, int i){//i表示第i个结点
    //经过顺序调换，使该元素的根结点为最大值
    if (i < length)
    {
        //i结点的左右孩子结点下标lChild，rChild
        int lChild = 2 * i + 1;
        int rChild = 2 * i + 2;
        int max = i;
        if (lChild < length && tree[max] < tree[lChild])
        {
            max = lChild;
        }

        if (rChild < length && tree[max] < tree[rChild])
        {
            max = rChild;
        }
        if (max != i)
        {
            swap(tree, max, i);
            //交换后，确保其子树也满足要求
            heapify(tree, length, max);
        }
    }
}
void buildHeap(int tree[], int length){
    int last   = length - 1;//最后一个结点
    int parent = ( last - 1 ) / 2;
    for (int i = parent; i >= 0; i--)
    {
        heapify(tree, length, i);
    }
}
void heapSort(int tree[] ,int length){
    buildHeap(tree, length);
    for (int i = length-1; i >= 0; i--)
    {
        swap(tree, i, 0);
        heapify(tree, i, 0);
    }
    
}

/**
 * 归并排序：测试用例：{49 ,38, 65, 97, 76, 13, 27, 49, 55, 4};
 * 思路：将数组一般对一般分开，然后合并
 * 时间复杂度 = 将数组分开的O(logn) * 将排列好的数据赋给原数据O(n)
 * */
/**
 * 思路:    1.定义一个空数组temp[]，长度与待合并数组一致，用于存放合并时的数据
 *          2.定义双指针i,j，分别从两段数据的开头（low,mid+1），开始比较，将较小的一个放入temp，直到遍历完一组数据
 *          3.将剩下的直接全部放入temp中
 *          4.将temp里的数据赋给原数组
 * */
void merge(int nums[], int low, int mid, int high){
    if (low < high)
    {
        int i = low, j = mid + 1;
        int* temp = (int*)malloc((high - low + 1) * sizeof(int));
        int k = 0;
        while (i <= mid && j <= high)
        {
            temp[k++] = (nums[i] <= nums[j]) ? nums[i++] : nums[j++];
        }
        while (i <= mid)
        {
            temp[k++] = nums[i++];
        }
        while (j <= high)
        {
            temp[k++] = nums[j++];
        }
        //将归并好的数据赋给nums[]
        for ( k = 0,i = low; i <= high; k++,i++)
        {
            nums[i] = temp[k];
        }
        
    }
}
void mergeSort(int nums[], int low, int high){
    if (low < high)
    {
        int mid = (low + high)/2;
        mergeSort(nums, low, mid);
        mergeSort(nums, mid + 1, high);
        merge(nums, low, mid, high);
    }
}

int main(){
    //直接插入排序
    // int nums[] = {8,2,4,7,6,9,5,1};
    // int length = getLength(nums);
    // insertSort(nums,length);
    // cout<<"直接插入排序:";
    // printArray(nums,length);

    //折半插入排序
    // int key = 3;
    // int array[length+1];
    // copyArray(nums,array,length);
    // binarySort(array,length+1,key);
    // cout<<"折半插入排序:";
    // printArray(array,length+1);

    //希尔排序
    int array[] = {49 ,38, 65, 97, 76, 13, 27, 49, 55, 4};
    int length = getLength(array);
    // xierSort(array, length, 1);
    
    //冒泡排序
    // bubbleSort(array,length);

    //快速排序
    // cout<<"快速排序前：";
    // printArray(array,length);
    // quickSort(array,0,length-1);
    // cout<<"快速排序后：";
    // printArray(array,length);

    //简单选择排序
    // cout<<"简单选择排序：";
    // printArray(array,length);
    // simpleSelectSort(array,length);
    // cout<<"简单选择排序：";
    // printArray(array,length);

    //堆排序
    // cout<<"堆排序排序前：";
    // printArray(array,length);
    // heapSort(array,length);
    // cout<<"堆排序排序后：";
    // printArray(array,length);

    //归并排序
    // cout<<"归并排序排序前：";
    // printArray(array,length);
    // mergeSort(array, 0, length-1);
    // cout<<"归并排序排序后：";
    // printArray(array,length);
    
    return 0;
}